Some undecidable things off topic:
I am away from my comfort zone here, so feel free to protest. Consider the line of reasoning:
Most horses have hooves.
Many sloths have three toes.
Therefore all crocodiles have wings.
I think we can agree that the line of reasoning is wrong.
And consider the line:
All parrots are birds.
Polly is a parrot.
Therefore Polly is a bird.
Sounds good to me.
Try, “This statement cannot be disproved.”
That one’s true. If you prove it, it’s wrong. You can’t prove something that’s wrong, so it can’t be proved so it’s true. And it is true. So there are statements that are true which cannot be proved to be true. A lot of us suspect that this is not the only case. It’s somewhere between right and wrong.
So try, “This statement is wrong.” If it’s wrong it’s right, and if it’s right it’s wrong. It’s somewhere between, “Cannot be proved,” and “Just plain wrong.” It’s undecidable.
Now I seem to be doomed to be, or maybe I take a malicious pleasure in, annoying as many people as I possibly can. I was delighted to learn, after having read a number of times, about the “stopping paradox” or something with a similar name.
There was a man named Alan Turing, who was involved with the British code cracking operation during WW II. The Germans had a code that involved a machine. There were an enormous number of possible settings on the machine. Once a setting was chosen, they’d type in the message. They’d transmit the encoded version, and the recipients, using the same settings, would type that in, and out would come the message in the clear. They were quite confident in their machine, not knowing that the Poles had managed to filch one and give it to the Brits. But even having the machine was not enough. They needed the settings.
So more or less they would try all the settings hoping to come up with the right ones before the day ended, and the settings would be changed. One of the parts of the machine they were using to crack the machine involved a long, endless paper tape with “Heil Hilter” on it and any number of words or phrases that were likely to come up. The tape whizzed around and around, each time entering bits of possible messages and once per cycle resetting the machine.
Turing thought about the fact that the tape was changing the program, and the program could potentially write on the tape, thus changing itself. They didn’t mention, but the machine could also potentially erase points on the tape. So Turing devised a machine, based on that tape, which could reprogram itself depending on the results of it’s calculations. This was the Turing Machine, the first design for a general programmable computer. Now we generally use electronics. The real tape, of course would occasionally break and shower the whole works with confetti.
Turing went on to prove that his general purpose machine could do anything any computer could do. It would just take longer. And so it is to this day. Any computer you see is a Turing machine.
And then, giggle, Turing proved that there was no general algorithm (read “program”) that could predict what all other programs could do without running them. The “stopping paradox” asks whether a program will eventually stop or will it run on forever. For instance Give the machine instructions: Take the number 1. Add 1. If the result is 3, stop. Otherwise subtract 1. Go back to the Add 1 instruction. Obviously the program will not stop. And obviously you could program a computer to spot that pattern and say so. But it can’t spot all such patterns.
C++ is a language designed among other things to prevent just that sort of problem. I don’t know if you could write a non-stopping program in C++, but it would be very tricky.
The bottom line is that a computer cannot really deal in abstract reasoning. That’s where I get to annoy my friends. Some of them believe it’s all science. Science can explain everything. But I say anything in science can be entered into a computer. And computers can’t do abstract reasoning. So science can never describe everything.
There’s some billion dollars being spent on figuring how the brain works. I crow, “Can’t be done. The brain uses abstract reasoning. That’s how they knew to look for “Heil Hitler.” So they’ll never figure that out. In all honesty, I’m not so sure.
I’m not sure the brain really is capable of abstract reasoning. It may be that we have up there a bunch of routines for determining things in a way that looks like abstract reasoning. It may be wired in, like the way to detect this or than endless loop in a computer program.
But I leave them the glory of figuring that out and annoying me.
Anyway, I guess I’ve said all this before, there is now a BRAND NEW WAY TO WRITE AN UNDECIDABLE QUESTION. (Cubitt et al. “Undecidability of the Spectral Gap Nature vol. 528 no. 7581 December 10, 2015 page 207) It uses the language of quantum mechanics. I suppose I ought to same something about the “spectral gap.”
I’m sure you know that if you accelerate an electrical charge, for instance run it up and down a radio mast go get a radio wave or just heat it up so it bounces around to get light from an old incandescent light bulb filament, electro-magnetic radiation is produced. That’s why we don’t say an electron travels around the nucleus of an atom. If it ran in a circle it would give off radiation and spiral in to the center. There are only certain “orbitals” an electron can occupy, named K, L, M and so forth. I don’t know why they started with K. An electron can absorb or give off radiation when it changes orbitals.
The radiation change between any two orbitals is fixed and corresponds with a line on the spectrum. The spectral gap is just the difference between the K orbital and the electron lying on the nucleus. So is there a spectral gap in real life? Always. But could you design an atom using the equations of quantum mechanics that would not have such a gap? The answer turns out to be yes. And can you always tell from the equations whether there will be such a gap? It now turns out that the answer is no. It is another class of undecidable questions.
Now can I annoy somebody with this one before he or she loses interest? I can’t decide. I doubt it.
There have been 196 visitors over the past month and YouTube has run “Babies Triumph over Evil” 199 times.